/*
 * DepthFirstSearch.java
 * 
 * TCSS 435 - Autumn 2012
 * Homework 1
 */

import java.util.*;

/**
 * An depth first search for use with an iterative deepening depth first search based
 * upon a depth first search created by Matthew Alden.
 * 
 * @author Matthew Alden
 * @author Dallas Rosson
 * @version Autumn 2012
 */
public class DepthFirstSearch {
	public static List<State> solve(State start, State goal, int depth) {
		// LIFO collection of nodes that have not been explored.
		Stack<State> frontier = new Stack<>();
		// Collection (with fast search) holding nodes in the current search
		// path or in the frontier.  Each node maps to its parent node.
		Map<State,State> pathAndFrontier = new HashMap<>();
		// If the DFS has backtracked, records the State backtracked from
		// (null otherwise).
		State backtrackFrom = null;
		// The total number of nodes explored.
		int nodesExplored = 0;
		// The total number of nodes that have been in the frontier.
		int nodesInFrontier = 0;
		// The total number of nodes created.
		int nodesCreated = 0;
		// The path to the goal node.
		List<State> path = new LinkedList<State>();
		// The depth counter.
		int depthCounter = 0;
		// The child counter;
		int childCounter = 1;

		frontier.add(start);
		pathAndFrontier.put(start, null);
		nodesInFrontier++;
					
outer:	while (!frontier.isEmpty() && depthCounter <= (depth) * childCounter) {
		
			State node = frontier.pop();
			nodesExplored++;
			
			if (backtrackFrom != null) {

				State nodeParent = pathAndFrontier.get(node);
				
				do {
					
					System.out.println("Going up a level");
					depthCounter--;
					backtrackFrom = pathAndFrontier.remove(backtrackFrom);
					
				} while (backtrackFrom != nodeParent);
			}
			
			backtrackFrom = node;
				
			Iterable<State> hasChildren = node.getNeighbors();
			
			if (hasChildren.iterator().hasNext()) {
				
				for (State child : node.getNeighbors()) {
					
					System.out.println("Node: " + node + " Child: " + child);
					nodesCreated++;
				
					if (!pathAndFrontier.containsKey(child)) {
					
						if (depthCounter == 1) { // Counts the number maximum number of children a node can have.
							
							childCounter++;
						}
						
						if (depthCounter < depth) { // Ensures that the DFS backtracks when the maximum depth is reached.

							frontier.add(child);

							backtrackFrom = null;
						}
						
						pathAndFrontier.put(child, node);
					
						if (child.equals(goal)) {
						
							path = createPath(child, pathAndFrontier);
							displaySolutionPath(child, pathAndFrontier, path);
							break outer;
						}
				
					}
				}
			}

			System.out.println("Frontier: " + frontier.toString() + "\n");

			depthCounter++;
		}	
			

		System.out.println("   Nodes explored: " + nodesExplored);
		System.out.println("Nodes in frontier: " + nodesInFrontier);
		System.out.println("    Nodes created: " + nodesCreated);
		System.out.println("\n\n");
		
		return path;

	}
	
	public static void displaySolutionPath(State node, Map<State,State> parentMap, List<State> path) {

		System.out.println("\n\n\n\n\n");
		System.out.println("---------- Solution Found ----------");
		
		for (State puzzle : path)
			System.out.println(puzzle);
		System.out.println("Solution in " + (path.size() - 1) + " moves.");
	}
	
	/**
	 * Creates a list representing the path to the node holding the goal state.
	 * 
	 * @param node The node that contains the goal state.
	 * @param parentMap The collection holding the nodes of the current search path.
	 * @return A list representing the path to the node holding the goal state.
	 */
	private static List<State> createPath(State node, Map<State,State> parentMap) {
		
		LinkedList<State> path = new LinkedList<>();
		
		while (node != null) {
			path.addFirst(node);
			node = parentMap.get(node);
		}
		return path;
	}
}
